package com.wmx.datastructuresandalgorithms;

import java.util.Stack;

public class DoubleLinkedList {

    private Node head ;

    class Node{
        private Object data ; //data 域
        private Node next ;  //next 下一个节点域
        private Node pre ; //pre 上一个节点域
        Node(Object data){
            this.data = data ;
        }
    }

    //获得头部节点
    public Node getHadeNode(){
        return head;
    }

    //添加双向链表的元素
    public void add (Object data ){
        Node newNode = new Node(data);
        if(head == null){
            head = newNode;
            return;
        }
        Node current = head ;

        current.pre = newNode;

        newNode.next = current ;

        head = newNode;

    }

    //添加有序双向链表
    public void  addOrderBy(Object data){
        Node newNode = new Node(data);
        Node current = head;
        if(current == null){
            head = newNode;
            return;
        }


        Node previous = null ;
        while (current!= null && (int)current.data < (int)data){
            previous = current;
            current  = current.next;
        }



        if(previous == null){
            newNode.next = current; //头部节点加在新对象
            current.pre =newNode; //头部节点的上一个节点为新对象
            head  = newNode ; // 从头部插入元素

        }else {
            newNode.pre = previous; //形成双向链表
            newNode.next = previous.next;
            previous.next = newNode;
        }

    }


    //双向链表可以自我删除 找到删除的节点 temp ： temp.pre.next = temp.next   temp.pre = temp.next.pre
    //目前删除头部会报错
    public Node del(Node head,int data){
       if(head == null){
           return head;
       }
       if(head.next==null&&(int)head.data ==(int)data){

          head = null;
          return head;
       }
       Node current = head;
       Node previous = null;
       while (true){
              if((int)current.data == (int)data){
                  previous = current;
              }
              if(current.next == null){
                  break;
              }

               current = current.next;
       }

       if(previous == null){
           System.out.printf("没有找到元素");
       }else {

           previous.pre.next =previous.next;
           if(previous.next !=null){
               previous.next.pre = previous.pre;
           }

       }
       return head;
    }


    //查看链表中的数据

    public void  display(Node head){
        if(head == null){
            System.out.printf("链表中的数据为空");
            return;
        }
        Node current =head ;
        System.out.printf("[");
        while (true){
            if(current.next == null){
                System.out.printf(current.data+"]");
                break;
            }
            System.out.printf(current.data+"->");
            current = current.next;

        }

    }


    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.addOrderBy(2);
        doubleLinkedList.addOrderBy(1);
        doubleLinkedList.addOrderBy(4);
        doubleLinkedList.addOrderBy(99);
        doubleLinkedList.addOrderBy(8);
        doubleLinkedList.addOrderBy(111);
        doubleLinkedList.addOrderBy(8);
        Node headNode= doubleLinkedList.getHadeNode();

        doubleLinkedList.display(headNode);


       // doubleLinkedList.del(headNode,99);

        doubleLinkedList.display(doubleLinkedList.del(headNode,111));




    }


}
